package codeRandomThoughts.Test105从前序与中序遍历序列构造二叉树;

import codeRandomThoughts.utils.TreeNode;

import java.util.Arrays;

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //前序数组为空,说明根结点为空
        if (preorder.length == 0) {
            return null;
        }

        //前序数组第一个元素为根节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);

        //查询根节点在中序数组中的index
        int index = -1;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                index = i;
                break;
            }
        }

        //根据index分割中序数组 分为leftInorder 和 rightInorder
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
        int[] rightInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);

        //根据leftInorder的长度 分割前序数组 分割为 leftPreorder 和 rightPreorder
        int[] leftPreorder = Arrays.copyOfRange(preorder,1,leftInorder.length+1);
        int[] rightPreorder = Arrays.copyOfRange(preorder,leftInorder.length+1, preorder.length);

        //让根节点的左右子树分别指向递归函数
        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        //返回根节点
        return  root;
    }

}
